package leetcode.editor.cn.dp;

//一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。 
//
// 给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。 
//
// 开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。 
//
// 如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
// 
//
// 
//
// 示例 1： 
//
// 
//输入：stones = [0,1,3,5,6,8,12,17]
//输出：true
//解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然
//后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。 
//
// 示例 2： 
//
// 
//输入：stones = [0,1,2,3,4,8,9,11]
//输出：false
//解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。 
//
// 
//
// 提示： 
//
// 
// 2 <= stones.length <= 2000 
// 0 <= stones[i] <= 231 - 1 
// stones[0] == 0 
// 
// Related Topics 动态规划 
// 👍 284 👎 0

class FrogJump {
    public static void main(String[] args) {
        Solution solution = new FrogJump().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * @Time:
         * @Space:
         * @Author: 赖锦帆
         * @Date: 2021-04-29 07:18
         * dp[i][k]表示从第0个石头走到第i个石头，上一步走了k步的情况是否可能
         * base case：dp[0][0]=true,其他dp[i][0]=false
         * 求dp[n-1][k]是否存在任意一个为true
         * <p>
         * dp[i][k] = dp[j][k-1]||dp[j][k]||dp[j][k+1]
         * j满足 j<i,且有唯一j使stones[i]-stones[j] = k
         * 满足子结构
         */

        public boolean canCross(int[] stones) {
            boolean[][] dp = new boolean[stones.length][stones.length];
            dp[0][0] = true;
            int n = stones.length;
            //从第0个石头开始遍历到最后一个石头
            for (int i = 0; i < n; i++) {
                //遍历到第i个石头上一次步数k的可能性
                //(k的几种可能性取决于当前位置i与上一次从第j个石头跳来，单值映射，所以可以用j替代k，
                // 而使用单值映射替代时应该注意两变量范围不同引起越界，如果直接用k遍历太耗时)
                // j从后往前为了在
                for (int j = i - 1; j >= 0; j--) {
                    int k = stones[i] - stones[j];
                    //到达当前位置上一次步数应该小于等于j+1,
                    if (k > j + 1)
                        break;
                    //三元二维dp
                    dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                    if (i == n - 1 && dp[i][k])
                        return true;
                }
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
